hill climbing with backtracking

Simple forgetful hill climbing constantly tries to look foer neighbouring places or states that are better than the surrent state, but keeps no track of where it has been. By adding backtracking hill climbing can deal impasses, when it cannot find suitable next states, or with local maxima by restarting from a previous state. If the hill-climbing is deterministic (chooisng the very best next step) the algorithm also has to keep track of what choices it made in the past otherwise it would simply repeat the same steps after backtracking! This is less important for stochasitic variants of hillclimbing (such as simulated annealing).